#include "stdlib.h"
#include "stdio.h"

#define OK 1
#define ERROR 0
typedef int Status; 
typedef int ELEMTYPE;
typedef struct _Node{
    ELEMTYPE data;
    struct _Node *next;
}Node, *LinkedList;

// void getLength(LinkedList list, int &length){
//     length = 0;
//     LinkedList p = list;
//     while(p->next){
//         length++;
//         p = p->next;
//     }
// }
void reverse(LinkedList &head){
    LinkedList cur = head->next;
    LinkedList pre = NULL;
    LinkedList next;
    while(cur){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    head->next = pre;
}
Status createByArray(LinkedList &head, int nums[], int n){
    head = (LinkedList) malloc(sizeof(Node));
    if(!head){
        return ERROR;
    }
    Node *tail = head;
    for(int i = 0; i < n; i++){
        Node *node = (LinkedList) malloc(sizeof(Node));
        node->data = nums[i];
        tail->next = node;
        tail = node;
    }
    tail->next = NULL;
    return OK;
}

/**
 * @brief find the sequence of the specified element in the linked list
 * 
 * @param list linked list
 * @param e element
 */
int findEle(LinkedList list, ELEMTYPE e){
    if(list == NULL || list->next == NULL)
        return ERROR;
    LinkedList p = list->next;
    int n = 1;
    while(p){
        if(p->data == e){
            return n;
        }
        n++;
        p = p->next;
    }
    return ERROR;
}

// int getElem(LinedList list, int i, ELEMTYPE &e){
//     int j = 1;
//     Node *p = list->next;
//     while(p && j < i){
//         j++;
//         p = p->next;
//     }

//     if(!p || i > j){
//         return 0;
//     }
//     e = p->data;
//     return 1;
// }

/**
 * @brief inserts the defined element into the list defined position
 * 
 * @param list linked list
 * @param i index(start from 1)
 * @param e element
 */
Status insert(LinkedList &list, int i, ELEMTYPE e){
    int j = 1;
    Node *p = list;
    while(j < i && p){
        j++;
        p = p->next;
    }
    if(j > i || !p){
        // printf("非法插入位置!");
        return ERROR;
    }
    Node *node = (LinkedList) malloc(sizeof(Node));
    node->data = e;
    node->next = p->next;
    p->next = node;
    return OK;
}

/**
 * @brief remove specified element from list
 * 
 * @param list linked list
 * @param e element
 */
Status removeEle(LinkedList &list, ELEMTYPE e){
    LinkedList p = list;
    while(p->next && p->next->data != e){
        p = p->next;
    }

    if(!p->next){   //没找到
        // printf("未找到 %d", e);
        return ERROR;
    }

    LinkedList temp = p->next;
    p->next = temp->next;
    free(temp);
    return OK;
    // printf("找到 %d,已删除", e);
}
// void del(LinedList &list, int i, ELEMTYPE &e){
//     int j = 1;
//     Node *p = list;
//     while(j < i && p){
//         j++;
//         p = p->next;
//     }
//     if(j > i || !p){
//         return;
//     }
//     Node *temp = p->next;
//     e = temp->data;
//     p->next = temp->next;
//     free(temp);
// }


void printLinkedList(LinkedList list){
    printf("\n");
    LinkedList p = list->next;
    while(p){
        printf("%d", p->data);
        p = p->next;
        //有下一个节点打印->
        if(p){
            printf("->");
        }
    }
    printf("\n");
}

// void createFromTail(LinedList &list, int nums[], int n){
//     list = (LinedList)malloc(sizeof(Node));
//     list->next = NULL;
//     for(int i = 0; i < n; i++){
//         Node *node = (LinedList) malloc(sizeof(Node));
//         node->data = nums[i];
//         node->next = list->next;
//         list->next = node;
//     }
// }
